package binary_tree.leetcode.easy;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author Stark
 * @description 二叉树的后序遍历
 * 题目链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
 * @date 2022/4/14 17:10
 **/
public class Num145_PostorderTraversal {
    int choice = 1;
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(choice == 1){
            if(root == null)
                return list;
            if(root.left != null)
            if(root.right != null)
            list.add(root.val);
            return list;
        }else if(choice == 2){
            if(root == null)
                return list;
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode cur = root;
            //用于保存上一个操作过的结点
            TreeNode prev = null;
            //cur这里的判空只是为了进入循环
            while(cur != null || !stack.isEmpty()){
                //一路向左,保存结点
                while(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                //如果右子树为空或已经处理过了
                //就直接将值添加到list中
                if(cur.right == null || cur.right == prev){
                    list.add(cur.val);
                    //prev保存了上一个操作过的结点
                    prev = cur;
                    //置空,为了下次循环处理下一个结点,不压栈
                    cur = null;
                }else {
                    //否则再将出入压入栈中,操作右结点
                    stack.push(cur);
                    cur = cur.right;
                }
            }
            return list;
        }
        return list;
    }
}
